package com.lihepeng.leecode.tree.langbuladong;

import com.lihepeng.leecode.tree.TreeNode;

import java.util.LinkedList;

/**
 * @link main.java.leecode.tree.langbuladong.Solution297
 * 使用后续遍历的方式完成
 */
public class Solution297_1 {
    // Encodes a tree to a single string.
    private static final String SEP = ",";
    private static final String EMPTY = "#";
    StringBuffer sb = new StringBuffer();
    public String serialize(TreeNode root) {
        if (root==null){
            sb.append(EMPTY).append(SEP);
            return null;
        }

        serialize(root.left);
        serialize(root.right);
        // 后续遍历模板
        sb.append(root.val).append(SEP);

        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        // 将字符串转换成列表
        LinkedList<String> nodes = new LinkedList<>();
        for (String item:data.split(",")) {
            nodes.add(item);
        }
        return deserialize(nodes);
    }

    public TreeNode deserialize(LinkedList<String> nodes ) {
        // 需要找到根节点
        if (nodes.isEmpty()){
            return null;
        }
        // 列表最左边的元素为根节点
        String s = nodes.removeLast();
        if (EMPTY.equals(s)){
            return null;
        }
        TreeNode rootNode = new TreeNode(Integer.parseInt(s));
        rootNode.right = deserialize(nodes);
        rootNode.left = deserialize(nodes);
        return rootNode;
    }
}
